import heapq
from typing import List


class Solution:
    def maximumMinimumPath(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def _is_valid(x, y):
            return 0 <= x < m and 0 <= y < n

        def neighbors(x1, y1):
            return [(x2, y2) for (x2, y2) in [(x1 - 1, y1), (x1 + 1, y1), (x1, y1 - 1), (x1, y1 + 1)]
                    if _is_valid(x2, y2)]

        ans = grid[0][0]

        visited = {(0, 0)}
        queue = [(-grid[0][0], 0, 0)]

        while queue:
            v1, i1, j1 = heapq.heappop(queue)
            ans = min(ans, -v1)

            if i1 == m - 1 and j1 == n - 1:
                return ans

            for i2, j2 in neighbors(i1, j1):
                if (i2, j2) not in visited:
                    visited.add((i2, j2))
                    heapq.heappush(queue, (-grid[i2][j2], i2, j2))

        return ans


if __name__ == "__main__":
    # 4
    print(Solution().maximumMinimumPath([[5, 4, 5], [1, 2, 6], [7, 4, 6]]))

    # 2
    print(Solution().maximumMinimumPath([[2, 2, 1, 2, 2, 2], [1, 2, 2, 2, 1, 2]]))

    # 3
    print(Solution().maximumMinimumPath(
        [[3, 4, 6, 3, 4], [0, 2, 1, 1, 7], [8, 8, 3, 2, 7], [3, 2, 4, 9, 8], [4, 1, 2, 0, 0], [4, 6, 5, 4, 3]]))
